/*
 * @Author: szx
 * @Date: 2022-05-05 13:50:37
 * @LastEditTime: 2022-05-05 14:23:14
 * @Description:
 * @FilePath: \leetcode\剑指offerII\109\109.js
 */
/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
// var openLock = function (deadends, target) {
//     if (target === '0000') return 0;
//     const wordSet = new Set(deadends);
//     if (wordSet.has('0000')) return -1;
//     const queue = [];
//     const visited = new Set();
//     queue.push(['0000', 1]);
//     while (queue.length) {
//         const [word, level] = queue.shift();
//         if (word == target) return level;
//         for (let i = 0; i < 4; i++) {
//             for (let c = '0'; c <= '9'; c++) {
//                 const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1); // 形成新词
//                 if (!wordSet.has(newWord) && !visited.hasnewWord)) {
//                     // 单词表里有这个新词
//                     queue.push([newWord, level + 1]); // 作为下一层的词入列
//                     visited.push(newWord)
//                 }
//             }
//         }
//     }
//     return -1; // bfs结束，始终没有遇到终点
// };

var openLock = function (deadends, target) {
    if (target === '0000') return 0;
    const dead = new Set(deadends);
    if (dead.has('0000')) return -1;
    let step = 0;
    const queue = ['0000'],
        visited = new Set();
    visited.add('0000');

    while (queue.length) {
        ++step;
        const size = queue.length;
        for (let i = 0; i < size; ++i) {
            const status = queue.shift();
            for (const nextStatus of get(status)) {
                if (!visited.has(nextStatus) && !dead.has(nextStatus)) {
                    if (nextStatus === target) return step;
                    queue.push(nextStatus);
                    visited.add(nextStatus);
                }
            }
        }
    }
    return -1;
};

// 枚举 status 通过一次旋转得到的数字
const get = (status) => {
    const numPrev = (x) => (x === '0' ? '9' : parseInt(x) - 1 + '');
    const numSucc = (x) => (x === '9' ? '0' : parseInt(x) + 1 + '');
    const ret = [];
    const array = Array.from(status);
    for (let i = 0; i < 4; ++i) {
        const num = array[i];
        array[i] = numPrev(num);
        ret.push(array.join(''));
        array[i] = numSucc(num);
        ret.push(array.join(''));
        array[i] = num;
    }
    return ret;
};
